import java.util.PriorityQueue;

public class Text3 {
    //找到前n个最小的
    public static int[] smallestK1(int[] arr,int k){
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for (int i = 0; i < k; i++) {
            int val=minHeap.poll();
            tmp[i]=val;
        }
        return tmp;
    }//时间复杂度O（（n+k）*log2(n)）

    //优化
    /*
    1,先把k个元素，建立一个大小为k的大根堆
    2，堆顶元素大于当前下标的元素，出堆
     */
    public static int[] smallestK(int[] arr,int k){
        int[]tmp=new int[k];
        if (k==0){
            return tmp;
        }
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new intCmp());
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int val=maxHeap.peek();
            if (val>arr[i]){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }

        }
        for (int i = 0; i < k; i++) {
            tmp[i]= maxHeap.poll();
        }
        return tmp;
    }//时间复杂度0（n*log2(k)）
    public static void main(String[] args) {

    }
}
